1. Field of the Invention
The present invention relates generally to automatic integrated circuit placement and routing tools, and more particularly to timing-driven layout algorithms for standard-cell and gate-array design.
2. Description of the Prior Art
Traditional approaches for timing-driven layout include a net constraint approach and a path constraint approach.
In the net constraint approach, a user specifies fixed net constraint values across a design to guide a layout program. The strength of this approach is that it generally does not require much overhead in the run time, and thus commonly referred to as being a "fast" approach. However, its weaknesses include a difficulty in providing "good" net constraint values, and an inflexibility in sharing timing resources among several nets. A timing resource is a portion of the overall delay to be distributed through a physical layout. Different paths usually share common nets, thus complicating the problem. A burden is placed on a designer to divide path delays into net delays, albeit without much information as how the nets will eventually be physically laid out. This approach also includes the problem that such net
delay constraints become fixed constraints, and cannot be altered during layout. In a case where one of the nets in the path takes up a shorter than expected delay, there is no way to share this extra timing resource with other nets in the same path that have run into difficulty in meeting their own respective constraints.
Due to such severe drawbacks, the common way to use this approach involves having the designers constrain several timing critical nets, and hope that the overall timing target can still be met. In older semiconductor fabrication technology this was not a severe problem, the feature size of the silicon was larger and the parasitic delays, the so-called layout or interconnect delays, were smaller. If a designer was well disciplined during the logic design phase in taking the timing into consideration, even this approach can suffice for some lesser timing-restrictive circuits. However, as technology advances and the feature size of the silicon process becomes smaller, e.g. the sub-micron range, parasitic delays are becoming a principal timing concern, and traditional net constraint approaches are inadequate.
The path constraint approach, tries to constrain the whole path, not individual nets, to meet a timing target, represented as path delays. The relationships among different timing paths are complicated, and even a simple move of a cell location during the running of a layout program can affect the delays of many nets. This, in turn, can require a reevaluation of the delays on numerous paths. The extra overhead required for this kind of delay evaluation during a single run of layout can provoke millions of cell movements. This is why the number of path constraints has to be limited to a small number to make this approach practical, e.g., where a solution can be found in finite time.
Due to such drawbacks, designers commonly only constrain several of what they think may be the most critical of paths. However, there is no guarantee that these constraints will be satisfied by the layout program. Other unconstrained paths, which may comprise over 90% of the total paths, may not remain well behaved and can become new critical paths.